#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# 60906 2021/2/2
# 并查集 union-find

class Solution10(object):
    def numSimilarGroups(self, strs):
        N = len(strs)
        uf = UF(N)
        # 两两判断连接(相似)
        for i in range(N):
            for j in range(i+1, N):
                if self.isSimilar(strs[i], strs[j]):
                    uf.union(i, j)

        print(uf)
        return uf.count


    def isSimilar(self, a, b):
        count = 0
        for i in range(len(a)):
            if a[i] != b[i]:
                count += 1
        return count == 2 or count == 0


class UF:
    def __init__(self, N):
        # 初始有 N 个连通分量，即一个字符一个连通分量
        # parents 每个位置指向了它的父
        self.id = list(range(N))
        self.count = N

    # 寻根
    def find(self, x):
        # while 方式也可以找到根，但不能重定义连接，让下次find效率提升
        # while self.id[x] != x:
        #     x = self.id[x]
        # return x
        # 1）寻根；2）路径上所有节点连接重置为直接指向根节点。
        if x != self.id[x]:
            # 高! 路径上所有节点都改为直接指向根节点. 这样下次 find 效率瞬间提升
            self.id[x] = self.find(self.id[x])
        return self.id[x]

    # 在同一颗树上时, 什么也不做; 否则, 归并两个树.
    # 是否在同一颗树上的依据: 同一个根.
    def union(self, u, v):
        uroot = self.find(u)
        vroot = self.find(v)
        if uroot == vroot:
            return
        # 合并两个树
        self.id[uroot] = vroot
        self.count -= 1

    # def count(self):
    #     return self.count
    def __str__(self):
        s = ""
        for (ix,item) in enumerate(self.id):
            s += str(ix) + "->" + str(self.id[item]) + "\n"
        return s

if __name__ == '__main__':
    # strs = ["tars", "rats", "arts", "star"]
    # strs = ["kccomwcgcs", "socgcmcwkc", "sgckwcmcoc", "coswcmcgkc", "cowkccmsgc", "cosgmccwkc", "sgmkwcccoc", "coswmccgkc", "kowcccmsgc", "kgcomwcccs"]
    # strs = ["blw","bwl","wlb"]
    strs = ["qihcochwmglyiggvsqqfgjjxu","gcgqxiysqfqugmjgwclhjhovi","gjhoggxvcqlcsyifmqgqujwhi","wqoijxciuqlyghcvjhgsqfmgg","qshcoghwmglygqgviiqfjcjxu","jgcxqfqhuyimjglgihvcqsgow","qshcoghwmggylqgviiqfjcjxu","wcoijxqiuqlyghcvjhgsqgmgf","qshcoghwmglyiqgvigqfjcjxu","qgsjggjuiyihlqcxfovchqmwg","wcoijxjiuqlyghcvqhgsqgmgf","sijgumvhqwqioclcggxgyhfjq","lhogcgfqqihjuqsyicxgwmvgj","ijhoggxvcqlcsygfmqgqujwhi","qshcojhwmglyiqgvigqfgcjxu","wcoijxqiuqlyghcvjhgsqfmgg","qshcojhwmglyiggviqqfgcjxu","lhogcgqqfihjuqsyicxgwmvgj","xscjjyfiuglqigmgqwqghcvho","lhggcgfqqihjuqsyicxgwmvoj","lhgocgfqqihjuqsyicxgwmvgj","qihcojhwmglyiggvsqqfgcjxu","ojjycmqshgglwicfqguxvihgq","sijvumghqwqioclcggxgyhfjq","gglhhifwvqgqcoyumcgjjisqx"]
    c = Solution10().numSimilarGroups(strs)
    print("count: " + str(c))
